1. Field of the Invention
This invention pertains to systems for recovering original signal information or content by processing multiple measurements of a set of mixed signals. More specifically the invention pertains to adaptive systems for recovering several original signals from received measurements of their mixtures. In order to understand the problem solved by the invention, and the approach of the prior art to solve this problem, the following problem statement is helpful: With reference to FIG. 1 of the attached drawings, consider N independent signals s1(t), . . . , and SN(t). These signals may represent any of, or a combination of, independent speakers or speeches, sounds, music, radio-based or light based wireless transmissions, electronic or optic communication signals, still images, videos, etc. These signals may be delayed and superimposed with one another by means of natural or synthetic mixing in the medium or environment through which they propagate. One consequently desires an architecture, framework, or device 20 that, upon receiving the delayed and superimposed signals, works to successfully separate the independent signal sources using a set of appropriate algorithms and procedures for their applications.
2. Discussion of Related Art
The recovery and separation of independent sources is a classic but difficult signal processing problem. The problem is complicated by the fact that in many practical situations, many relevant characteristics of both the signal sources and the mixing media are unknown.
Two main categories of methods are used:
1. Neurally inspired adaptive algorithms (e.g., U.S. Pat. Nos. 5,383,164 and 5.315,532), and
2. Conventional discrete signal processing (e.g., U.S. Pat. Nos. 5,208,786 and 5.539,832).
Neurally inspired adaptive arhitectures and algorithms follow a method originally proposed by J. Herault and C. Jutten, now called the Herault-Jutten (or HJ) algorithm. The suitability of this set of methods for CMOS integration have been recognized. However, the standard HJ algorithm is at best heuristic with suggested adaptation laws that have been shown to work mainly in special circumstances. The theory and analysis of prior work pertaining to the HJ algorithm are still not sufficient to support or guarantee the success encountered in experimental simulations. Herault and Jutten recognize these analytical deficiencies and they describe additional problems to be solved. Their proposed algorithm assumes a linear medium and filtering or no delays. Specifically, the original signals are assumed to be transferred by the medium via a matrix of unknown but constant coefficients. To summarize, the Herault-Jutten method (i) is restricted to the full rank and linear static mixing environments, (ii) requires matrix inversion operations, and (iii) does not take into account the presence of signal delays. In many practical applications, however, filtering and relative delays do occur. Accordingly, previous work fails to successfully separate signals in many practical situations and real world applications.
Conventional signal processing approaches to signal separation originate mostly in the discrete domain in the spirit of traditional digital signal processing methods and use the statistical properties of signals. Such signal separation methods employ computations that involve mostly discrete signal transforms and filter/transform function inversion. Statistical properties of the signals in the form of a set of cumulants are used to achieve separation of mixed signals where these cumulants are mathematically forced to approach zero. This constitutes the crux of the family of algorithms that search for the parameters of transfer functions that recover and separate the signals from one another. Calculating all possible cumulants, on the other hand, would be impractical and too time consuming for real time implementation.
The specifics of these methods are elaborated in these categories below.
These set of neurally inspired adaptive approaches to signal separation assume that the xe2x80x9cstatistically independentxe2x80x9d signal vector S(t)=[s1(t), . . . , and sN(t)]T is mixed to produce the signal vector M(t). The vector M(t) is received by the sensors (e.g, microphones, antenna, etc.).
Let the mixing environment be represented by the general (static or dynamic) operator ℑ. Then,
M(t)=ℑ(S(t))xe2x80x83xe2x80x83Equation (1)
There are several formulations that can be used to invert the mixing process, i.e., operator ℑ in a xe2x80x9cblindxe2x80x9d fashion where no apriori knowledge exists as to the nature or content of the mixing operator ℑ or the original sources S(t). We group these into two categories, static and dynamic. Additional distinctions can be made as to the nature of the employed adaptation criteria, e.g., information maximization, minimization of high order cumulants, etc.
1.1. The Static Case
The static case is limited to mixing by a constant nonsingular matrix. Let us assume that the xe2x80x9cstatistically independentxe2x80x9d signal vector S(t)=[s1(t), . . . , and sN(t)]T is mixed to produce the signal vector M(t). Specifically, let the mixing operator ℑ be represented by a constant matrix A, namely
M(t)=AS(t)xe2x80x83xe2x80x83Equation (2)
In FIG. 2, two architectures that outline the modeling of the mixing and the separation environments and processes are shown. The architecture in FIG. 2(a) necessarily computes the inverse of the constant mixing matrix A, which requires that A is invertible, i.e., Axe2x88x921 exists.
The alternate architecture in FIG. 2(b) does not impose this restriction in that upon convergence the off diagonal elements of the matrix D are exactly those of the off diagonal elements of the matrix A. In this case, however, diagonal elements of the matrix A are restricted to equal xe2x80x9c1.0.xe2x80x9d By setting the diagonal elements of D to zero, one essentially concludes that the mixing process is invertible even if the mixing matrix is not.
In both cases, S(t) is the set of unknown sources, M(t) is the set of mixtures, U(t) is the set of separated signals that estimate S(t), and Y(t) is the set of control signals used to update the parameters of the unmixing process. As shown in FIG. 2, the weight update utilizes a function of the output U(t).
In the first case, we labeled the unmixing matrix W, and in the second case we labeled it D. Note that D has zero diagonal entries. The update of the entries of these two matrices is defined by the criteria used for signal separation, discrimination or recovery, e.g., information maximization, minimization of higher order cumulants, etc.
As an example, one possible weight update rule for the case where
U(t)=WM(t)xe2x80x83xe2x80x83Equation (3)
could be
{dot over (w)}ij=xcex7[Wxe2x88x92T+gxe2x80x3(u)/gxe2x80x2(u)MT]ijxe2x80x83xe2x80x83Equation (4)
where xcex7 is sufficiently small, g is an odd function, and M is the set of mixtures, U is the set of outputs which estimate the source signals, subscript T denotes transpose, and xe2x88x92T denotes inverse of transpose. Note that the function g( ) plays an additional role in the update which can be related to the above diagram as
Y(t)=g(U(t))xe2x80x83xe2x80x83Equation (5)
One uses Equation (4) to update the entries of W in Equation (3). Through this is an iterative update procedure, the entries of W converge so that the product WA is nearly equal to the identity matrix or a permutation of the identity matrix.
On the other hand, in the second case, one potentially useful rule for the update of the D matrix entries dij is generically described as
{dot over (d)}ij=xcex7f(ui(t))g(uj(t))xe2x80x83xe2x80x83Equation (6)
where xcex7 is sufficiently small. In practice some useful functions for f(xc2x7) include a cubic function, and for g(xc2x7) include a hyperbolic tangent function. When using this procedure, one computationally solves for U(t) from Equation (7) below
U(t)=[I+D]xe2x88x921M(t)xe2x80x83xe2x80x83Equation (7)
at each successive step and sample point. This computation is a potentially heavy burden, especially for high dimensional D.
1.2. The Dynamic Case
The dynamic mixing model accounts for more realistic mixing environments, defines such environment models and develops an update law to recover the original signals within this framework.
In the dynamic case, the matrix A is no longer a constant matrix. In reference to the feedback structure of the static example, it is simpler to view Equation (7) where U(t)=[I+D]xe2x88x921M(t) as an equation of the fast dynamic equation
xcfx84{dot over (U)}(t)=xe2x88x92U(t)xe2x88x92DU(t)+M(t)xe2x80x83xe2x80x83Equation (8)
This facilitates the computation by initializing the differential equation in Equation (8) from an arbitrary guess. It is important however to ensure the separation of time scales between Equations (8) and the update procedure like the one defined by Equation (6). This may be ensured by making xcex7 in Equation (6) and xcfx84 in Equation (8) sufficiently small.
If we assume the dimensionality of M(t) is N, a set of differential equations that define the dynamic signal separation algorithm can be written as                                                         τ              i                        ⁢                          u              i                                =                                    -                              u                i                                      -                                          ∑                                  j                  ≠                  i                                            ⁢                              xe2x80x83                            ⁢                                                D                  ij                                ⁢                                  u                  i                                                      +                          m              i                                      ⁢                  
                ⁢                                            for              ⁢                              xe2x80x83                            ⁢              i                        =            1                    ,          ⋯          ,          N                                    Equation        ⁢                  xe2x80x83                ⁢                  (          9          )                    
This enumerates N differential equations. In addition, the adaptation process for the entries of the matrix D can be defined by multiple criteria, e.g., the evaluation of functions f( ) and g( ) in Equation (6). FIG. 3 is a pictorial illustration of the dynamic model in feedback configuration.
Current methods outline little in the way of procedures for the application of adaptation criteria within the architectures defined thus far. Two implied procedures have been noted:
First is the application of the signal separation functions, adaptation procedures and criteria to arbitrary points of dataxe2x80x94regardless of whether each of these points is practically and physically accessible or not. Thus, the adaptive separation procedure applies the adaptation functions and criteria to each element of the measured mixed signals individually and instantaneously, after which appropriate parameter updates are made.
The second type of procedure has been described in FIG. 2(a) that uses Equation (3). In this case, the criteria is applied to the entire data set, or selected data points from the entire data set. Thus, the related adaptation process does not progress per sample, but utilizes the whole data set over which a constant, static mixing matrix is assumed to apply. Although this method is somewhat more robust than the first, it is essentially an off-line method not suitable for real time signal separation. Furthermore, when the assumption of a static constant matrix is incorrect, the accuracy of the unmixing process suffers.
1.3. Feedforward State Space
The architecture is shown in FIG. 7. Let the n-dimensional source signal vector be s, and the m-dimensional measurement vector be M. The mixing environment may be described by the Linear Time-Invariant (LTI) state space:
{dot over ({overscore (X)})}={overscore (A)}{overscore (X)}+{overscore (B)}sM={overscore (C)}{overscore (X)}+{overscore (D)}sxe2x80x83xe2x80x83Equation (10)
The parameter matrices {overscore (A)}, {overscore (B)}, {overscore (C)} and {overscore (D)} are of compatible dimensions. This formulation encompasses both continuous-time and discrete-time dynamics The dot on the state {overscore (X)} means derivative for continuous-time dynamics, it however means xe2x80x9cadvancexe2x80x9d for discrete-time dynamics. The mixing environment is assumed to be (asymptotically) stable, i.e., the matrix {overscore (A)} has its eigenvalues in the left half complex plane. The (adaptive) network is proposed to be of the form
{dot over (X)}=AX+BMy=CX+DM,xe2x80x83xe2x80x83Equation (11)
where y is the n-dimensional output, X is the internal state, and the parameter matrices are of compatible dimensions. For simplicity, assume that X has the same dimensions as {overscore (X)}. FIG.(7) depicts the feedforward form of this framework.
The first question is the following: Does there exist parameter matrices A, B, C, and D which would recover the original signals? The answer now follows.
We state that the (adaptive) dynamic network would be able to counter act the mixing environment, if the network parameters are set at (or attain via an adaptive scheme) the following values:
A=A*=T({overscore (A)}xe2x88x92{overscore (B)}[D]{overscore (C)})Txe2x88x921xe2x80x83xe2x80x83Equation (12)
B=B*=T{overscore (B)}[D]xe2x80x83xe2x80x83Equation (13)
C=C*=xe2x88x92[D]{overscore (C)}Txe2x88x921xe2x80x83xe2x80x83Equation (14)
D=D*=[D]xe2x80x83xe2x80x83Equation (15)
where [D] equals
Dxe2x88x921: the inverse of D, if m=n,
({overscore (D)}T{overscore (D)})xe2x88x921Dxe2x88x92T; a pseudo-inverse, if m greater than n, and
Dxe2x88x92T({overscore (DD)}T)xe2x88x921: a pseudo-inverse if m less than n.
The matrices A*, B*, and C* can take on a family of values due to the nonsingular state-equivalent transformation T. We shall use T to render the network architecture xe2x80x9ccanonicalxe2x80x9d or simple from a realization view point. This formulation in effect generalizes the formulations in the literature, which are limited to FIR filters, predominantly for 2-dimensional sources and two measurements, into general n-dimensional sources, and m-dimensional measurements. Note that, this modeling includes the FIR filtering models, and extends to IIR filtering if A is nonzero.
While this feedforward form for the adaptive network is viable, we note a limitation for its applicability, namely, that the parameters of the mixing environment have to be such that the matrix A* is (asymptotically) stable. That is, for a stable mixing environment, the composite matrix of the adaptive network
A*={overscore (A)}xe2x88x92{overscore (B)}[D]{overscore (C)}xe2x80x83xe2x80x83Equation (16)
must be (asymptotically) stable, i.e., has its eigenvalues in the left half complex plane. It is apparent that this requirement places a limiting condition on the allowable mixing environments which may exclude certain class of applications!
The representation of signal mixing and separation by transfer functions makes this approach a dynamic environment model and method.
Current methods thus define a structure for separating two signals by processing two mixture measurements, which was illustrated in FIG. 4.
Other architectures for the separation functions in the transfer function domain results in three serious shortfalls which are all impediments to the design and implementation of a practical method and apparatus. First, this formulation, as expressed, precludes the generalization of the separation procedure to higher dimensions, where the dimensionality of the problem exceeds two. In other words, a practical formalization of the separation method does not exist when there are more than two mixtures and two sources. One can illustrate this by direct reference to other approaches, where matrix multiplication terms are written out, so that each scalar equation defines one of the entries of the resulting product matrix desired to be equal to zero. Since permutations of a diagonal matrix are also allowed, multiple sets of equations are created. For a two mixture problem, this results in two pairs (four total) of equations, each with two product terms. Beyond that the number of equations increases. To be precise the number of equations needed to describe the number of equations for a specific permutation of the N dimensional case is equal to (N2xe2x88x92N). For the two dimensional problem this value is 2.
Second, the inversion procedure for the transfer function is ad hoc and no recipe or teaching exists. The impact of dimensionality plays a crucial role in this. It is apparent from the method that the resulting architecture gives rise to networks requiring transfer components whose order is dependent on products of the transfer components of the mixing environment. Thus, one can not design a network architecture with a fixed order.
Third, the initial conditions can not be defined since the formulation is not in the time domain and can not be initialized with arbitrary initial conditions. Hence, the method is not suitable for real time or on line signal separation.
The present invention describes a signal processing system for separating a plurality of input signals into a plurality of output signals, the input signals being composed of a function of a plurality of source signals being associated with a plurality of sources, the output signals estimating the source signals or functions of source signals. The system comprises a plurality of sensors for detecting the input signals, an architecture processor for defining and computing a signal separation method, the signal separation method delimiting a signal separation architecture for computing the output signals, and an output processor for computing the output signals based on the signal separation method or architecture.